1. Field of the Invention
This invention relates generally to coordination amongst concurrent execution sequences in a multiprocessor, and more particularly, to a system and method for coordinating access to shared objects in a transactional memory space using nonblocking zero-indirection data objects.
2. Description of the Related Art
With the computer industry increasingly focusing on building multi-core processor chips, rather than making individual processors faster, it is increasingly important for everyday applications to be able to exploit multiple cores concurrently. In concurrent software designs and implementations, it is often important to ensure that one thread does not observe partial results of an operation that is concurrently being executed by another thread. Such assurances are important for practical and productive software development because, without them, it can be extremely difficult to reason about the interactions of concurrent threads. However, concurrent programming using traditional mechanisms such as locks and condition variables is subject to a number of serious pitfalls, including troublesome tradeoffs between performance, scalability, and software complexity.
Transactional memory is a paradigm that allows a programmer to design code as if multiple locations can be accessed and/or modified in a single atomic step. With transactional memory, programmers specify what should be executed atomically, leaving the system to determine how this is achieved. As typically defined, a transactional memory interface allows a programmer to designate certain sequences of operations as “atomic blocks”, which are guaranteed by the transactional memory implementation to either take effect atomically and in their entirety (in which case they are said to succeed), or have no externally visible effect (in which case they are said to fail). Thus, with transactional memory, it may be possible in many cases to complete multiple operations with no possibility of another thread observing partial results, even without holding any locks. The transactional paradigm can significantly simplify the design of concurrent programs.
Transactional Memory (TM) allows programmers to use transactional or atomic blocks, which may be considered sequential code blocks that should be executed atomically. In other words, executions of atomic blocks by different threads do not appear to be interleaved. To execute an atomic block, the underlying system may begin a transaction, execute the atomic block's memory accesses using that transaction, and then may try to commit the transaction. If the transaction commits successfully, the atomic block's execution seems to take effect atomically at the transaction's commit point. If it fails, the execution does not seem to take effect at all and the atomic block might be retried using a new transaction. It is the responsibility of the TM implementation to guarantee the atomicity of operations executed by transactions.
Transactional memory is widely recognized as a promising paradigm for allowing a programmer to make updates to multiple locations in a manner that is apparently atomic, while addressing many of the problems associated with the use of locks. In general, transactional memory can be implemented in hardware (HTM), with the hardware operating on shared memory in place and directly ensuring that a transaction is atomic, or in software (STM) that provides the “illusion” that the transaction is atomic, even though in fact it is executed in smaller atomic steps by the underlying hardware. While HTM solutions are generally faster than STM ones, “best effort” HTM may not be guaranteed to be able commit any particular transaction, in which case a programmer cannot rely solely on HTM, even if it is almost always effective.
Transactional memory implementations are typically classified as “blocking” or “nonblocking” depending on whether they allow the delay of one transaction to force another to wait indefinitely. Some object-based nonblocking STM systems suffer a substantial overhead for this advantage, as compared to blocking STMs.